#include "vector.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>
#include <assert.h>

static void Expand(vector *v)
{
  v->allocatedSize *= 2;
  v->root = realloc(v->root, v->allocatedSize * v->elemSize);
  assert(v->root != NULL);
}

void VectorNew(vector *v, int elemSize, VectorFreeFunction freeFn, int initialAllocation)
{
  assert(initialAllocation >= 0);
  if (initialAllocation == 0)  initialAllocation = kInitialAllocation; 
  v->root = malloc(elemSize * initialAllocation);
  assert(v->root != NULL); 
  v->elemSize = elemSize;
  v->logicalSize = 0;
  v->allocatedSize = initialAllocation;
  v->freefn = freeFn;   
}

void VectorDispose(vector *v)
{
  if (v->freefn != NULL) {
    for (int i = 0; i < v->logicalSize; ++i) 
      v->freefn((char *)v->root + v->elemSize * i); 
  }
  free(v->root);
}

int VectorLength(const vector *v)
{ return v->logicalSize; }

void *VectorNth(const vector *v, int position)
{ 
  assert(position >= 0 && position < v->logicalSize);
  
  return (char *)v->root + position * v->elemSize;
}

void VectorReplace(vector *v, const void *elemAddr, int position)
{
  assert(position >= 0 && position < v->logicalSize);
  char *elemPtr = VectorNth(v, position);
  if (v->freefn != NULL)  v->freefn(elemPtr);
  memcpy(elemPtr, elemAddr, v->elemSize);
}

void VectorInsert(vector *v, const void *elemAddr, int position)
{
  assert(position >= 0 && position <= v->logicalSize);
  if (v->logicalSize == v->allocatedSize)  Expand(v);
  
  char *elemPos = (char *)v->root + position * v->elemSize;
  if (position != v->logicalSize)
    memmove(elemPos + v->elemSize, elemPos, v->elemSize * (v->logicalSize - position));
  
  memcpy(elemPos, elemAddr, v->elemSize); 
  v->logicalSize++;  
}

void VectorAppend(vector *v, const void *elemAddr)
{
  VectorInsert(v, elemAddr, v->logicalSize);
}

void VectorDelete(vector *v, int position)
{
  assert(position >= 0 && position < v->logicalSize);
  
  char *dest = VectorNth(v, position);
  if (v->freefn != NULL) v->freefn(dest);

  char *src = dest + v->elemSize;

  if (position != v->logicalSize - 1)
    memmove(dest, src, v->elemSize * (v->logicalSize - position - 1));

  v->logicalSize--;
}

void VectorSort(vector *v, VectorCompareFunction compare)
{
  assert(compare != NULL);

  qsort((char *)v->root, v->logicalSize, v->elemSize, compare);
}

void VectorMap(vector *v, VectorMapFunction mapFn, void *auxData)
{
  assert(mapFn != NULL);
  
  for (int i = 0; i < v->logicalSize; ++i) 
    mapFn(VectorNth(v, i), auxData);
}

static const int kNotFound = -1;
int VectorSearch(const vector *v, const void *key, VectorCompareFunction searchFn, int startIndex, bool isSorted)
{ 
  assert(searchFn != NULL);
  assert(startIndex >= 0 && startIndex <= v->logicalSize);
  size_t size = v->logicalSize;
  char *elemFound = NULL;
  if (isSorted)
    elemFound = bsearch(key, (char *)v->root, size, v->elemSize, searchFn);
  else 
    elemFound = lfind(key, (char *)v->root, &size, v->elemSize, searchFn);

  if (elemFound != NULL)
	return (elemFound - (char *)v->root)/v->elemSize;

  return kNotFound; 
} 
